package com.future;

import java.util.HashMap;
import java.util.Map;

/**
 * Description:
 * 给定一个字符串s，计算具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是连续的。
 * <p>
 * 重复出现的子串要计算它们出现的次数。
 * <p>
 * 示例 1 :
 * <p>
 * 输入: "00110011"
 * 输出: 6
 * 解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
 * <p>
 * 请注意，一些重复出现的子串要计算它们出现的次数。
 * <p>
 * 另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
 * 示例 2 :
 * <p>
 * 输入: "10101"
 * 输出: 4
 * 解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
 * <p>
 * 提示：
 * <p>
 * s.length在1到50,000之间。
 * s只包含“0”或“1”字符。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-binary-substrings
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2021/10/18 15:03
 */
public class Solution_696 {

    public static void main(String[] args) {
        String s = "00110011";
        // 0011 01 1100 10 01 0011
        // 2222
        // 10101 10 01 10 01
        // 11111
        //s = "101011";
        s = "000111000"; // 000111 0011 01 11100 1100 10
        System.out.println(countBinarySubstrings(s));
        System.out.println("v2:" + countBinarySubstrings_v2(s));

    }

    /**
     * 题目理解：
     * 0、1不能断层
     * eg: 10101
     * 可以为：10 01 10 01
     * 不能为：1010，因为101的'1'出现断层了，不再连续，
     * 必须要保证一个字符串平均分成两半，每一边的字符串要么都是0、要么都是1
     *
     * @param s
     * @return
     */
    public static int countBinarySubstrings(String s) {
        Map<Integer, Integer> map = new HashMap<>();
        int N = s.length();
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            int count = 0;
            if ('0' == s.charAt(i)) {
                while (i < N && '0' == s.charAt(i)) {
                    count++;
                    i++;
                }
            } else {
                while (i < N && '1' == s.charAt(i)) {
                    count++;
                    i++;
                }
            }
            map.put(index, count);
            i--; // 上面++已经导致多走一步了，需要回退一步
            index++;
        }
        if (map.size() < 2) {
            return 0;
        }
        int result = 0;
        for (int i = 1; i < map.size(); i++) {
            /**
             * 重点
             * s = "000111000";
             * 000111 0011 01 11100 1100 10
             */
            result = result + Math.min(map.get(i - 1), map.get(i));
        }
        return result;
    }

    public static int countBinarySubstrings_v2(String s) {
        Map<Integer, Integer> map = new HashMap<>();
        int index = 0;
        int k = 0;
        while (k < s.length()) {
            int count = 0;
            char c = s.charAt(k);
            while (k < s.length() && c == s.charAt(k)) {
                ++count;
                ++k;
            }
            map.put(index, count);
            index++;
        }
        if (map.size() < 2) {
            return 0;
        }
        int result = 0;
        for (int i = 1; i < map.size(); i++) {
            /**
             * 重点
             * s = "000111000";
             * 000111 0011 01 11100 1100 10
             */
            result = result + Math.min(map.get(i - 1), map.get(i));
        }
        return result;
    }
}
